#include<iostream>
using std::endl;
using std::cout;

//交换函数
void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = a;
}
//两个指针
//按照思路，返回的是下一个的基准值
//我设置第一个为基准值
int partion(int *arr,int left,int right){
    //设置第一个为基准值
    int i = left;
    int j = right;
    int pox = arr[left]; 
    while(i<j){
        while(i<j&& pox<arr[j]){
            --j;
        }
        //跳出循环
        //保证基准值在右边 不然没必要做交换
        if(i<j){
            //swap(pox,arr[i]);
            swap(arr[i],arr[j]);
            i++;
        }
        while(i<j&&pox >= arr[j]){
            ++i;
        }
        if(i<j){
            swap(arr[i],arr[j]);
            j--;
        }
    }
    //返回一个基准值
    return i;
}
//递归函数
void Quick(int *arr,int left,int right){
    int mid; // 设置一个基准值
	if (left < right)
	{
		mid = partion(arr, left, right);  // 返回基准元素位置
		Quick(arr, left, mid - 1); // 左区间递归快速排序
		Quick(arr, mid+1, right); // 右区间递归快速排序
	}
}

template<class T>
void display(T &con){
    for(auto &ele:con){
        cout<<ele<<" ";
    }
    cout<<endl;
}


void test0(){
    int arr[] = {1,11,8,6,34,23,53,21};
    display(arr);
    Quick(arr,0,sizeof(arr)/sizeof(arr[0])-1);
    display(arr);
}
int main(void){
    test0();
}